/**
 * 原题 https://leetcode.com/problems/di-string-match/
 * <p>
 * 2种解法 ： 1.计数器+ 反转数组
 * 2. 贪心+ 双指针
 */
public class _942 {

    static class Solution1 {
        public int[] diStringMatch(String s) {
            //从有序中反转部分数组，反转之外的升序状态不会改变
            int[] res = new int[s.length() + 1];
            for (int i = 0; i < res.length; i++) {
                res[i] = i;
            }
            //反转 [i,i+count]
            int start = 0;
            int countD = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == 'D') {
                    countD++;
                } else {
                    reverse(res, start, start + countD);
                    start = i + 1;
                    countD = 0;
                }
            }
            if (countD != 0) {
                reverse(res, start, start + countD);
            }
            return res;

        }

        public void swap(int[] array, int i, int j) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }

        public void reverse(int[] array, int i, int j) {
            while (i < j) {
                swap(array, i++, j--);
            }
        }
    }

    static class Solution2 {
        public int[] diStringMatch(String s) {
            //大佬的贪心思路
            //左右指针，左指针为当前可用的最小值，右指针为当前可用的最大值
            //降低，用最大值为起点
            //上升用最小值为起点
            //这样一定符合
            int left = 0;
            int right = s.length();
            int[] res = new int[s.length() + 1];
            for (int i = 0; i < s.length(); i++) {
                res[i] = s.charAt(i) == 'I' ? left++ : right--;
            }
            res[res.length - 1] = left;
            return res;
        }
    }
}
